//
// Created by Jisam on 2024/8/20 8:34.
// Solution of   #DX0002. 星星
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <climits>

using namespace std;

#define endl "\n"
#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>

#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
#define code_by_jisam ios::sync_with_stdio(false),cin.tie(nullptr)
using namespace std;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1,};
int dy[] = {0, 0, -1, 1, 1, -1, -1, 1,};

int n, k;
i64 ans = INT_MAX;
const int maxn = 1000 + 5;

VVI vis(maxn, vector(5, 0)), ma(maxn, vector(5, 0));
//VI a(maxn),b(maxn),c(maxn),d(maxn);

void dfs(int i, i64 cur,i64 stars) {
    if (i >= n) { return; }
    if (stars > k) {return;}
    if (stars == k) {
        ans = min(ans, cur);
        return;
    }
    for (int j = 0; j < 5; j++) {
        if (vis[i][j]) continue;
        vis[i][j] = 1;
        cout << i << " " << cur << " " << ma[i][j] << endl;
        dfs(i + 1, cur + ma[i][j],stars + j + 1);
        vis[i][j] = 1;

    }
}

void solution() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> ma[i][0] >> ma[i][1] >> ma[i][2] >> ma[i][3];
    }
    dfs(0, 0,0);
    cout << ans <<endl;
}

int main() {
    code_by_jisam;
    int T = 1;
    cin >> T;
    while (T--) {
        solution();
    }
    return 0;
}